﻿/********************************************
 * 
 * Jim Trebbien
 * 
 * *****************************************/


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Model
{
    public class Graf
    {
        private Node Root;
       // public List<List<int>> Kanter; //vaerdien er vaegten/rejsetid
        public int[,] Kanter;
        
        private List<Node> Nodes = new List<Node>();

        public Graf()
        {
            //Kanter = new List<List<int>>();
            Nodes = new List<Node>(); 
        }

        public void DanGraf(int size)
        {
           // Kanter = new int[Nodes.Count, Nodes.Count];
            Kanter = new int[size,size];
        }


        //find et barn der ikke har vaeret besoegt
        private Node findEnsomtBarn(Node node) 
        {
            int index = Nodes.IndexOf(node);
            for (int i = 0; i < Nodes.Count; i++)
                if (Kanter[index,i] == 1 && !Nodes[i].VISITED)
                    return Nodes[i];
            return null;
        }

        public void AddNode(Node nynode)
        {
            Nodes.Add(nynode);
        }


        public void BredeFoerstTraversering(Node Start)
        {
            Queue<Node> q = new Queue<Node>();
            q.Enqueue(Start);
            udskrivNode(Start);
            Start.VISITED = true;
            while (q.Count != 0)  //hvor er isEmpty?
            {
                Node n = (Node)q.Dequeue();
                Node Child = null;
                while ((Child = findEnsomtBarn(n)) != null)
                {
                    Child.VISITED = true;
                    udskrivNode(n);
                    q.Enqueue(Child);
                }
            }

            rydOpiNodes(); //alle visited skal saettes til false

        }


        public int FindNode(string bynavn)
        {
            for (int i = 0; i < Nodes.Count; i++)
                if (Nodes[i].BYNAVN == bynavn)
                {
                    return i;
                }
                else return -1;
            
            return -1;
        }




        private void rydOpiNodes()
        {
            foreach(Node n in Nodes)
                n.VISITED = false;
        }








        /********************************************************************************************************************
         * 
         * 
         *                                                  MinimumSpanningTree
         * 
         * 
         * v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v-v*/


        private List<int> createIndex()
        {
            List<int> index = new List<int>(); //sorteret index ned kanter

            for (int i = 0; i < Kanter.Length; i++)
                for (int j = 0; j < Kanter.Length; j++)
                    if (Kanter[i,j] != null)
                        index.Add(Kanter[i,j]);

            index.Sort();
            int n = 0;
            while (n < index.Count - 1)
            {
                if (index[n] == index[n + 1])
                    index.RemoveAt(n);
                else
                    n++;
            }

            rydOpiNodes();
            return index;
        }


        public Graf MinimumSpanningTree(Graf g) 
        {
            Graf resultat = new Graf();
            resultat.Nodes = this.Nodes; //all nodes skal med

            List<int> index = createIndex();

            //tag den korteste, hvis ikke begge nodes er visited, add den til minTree og sæt Nodes til visited, ellers led videre
           

            for (int i = 0; i < index.Count; i++)
            {
                for(int j = 0; j<Kanter.Length;j++)
                    for (int t = 0; t < Kanter.Length; t++)
                    {
                        if (Kanter[j,t] == index[i])
                        {
                            if (!Nodes[j].VISITED || !Nodes[t].VISITED)
                            {
                                resultat.Kanter[j,t] = Kanter[j,t];
                                Nodes[j].VISITED = Nodes[t].VISITED = true;
                            }
                        }

                    }
            }
            return resultat;
        }


        /*^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^*/








        private void udskrivNode(Node node)
        {
            Console.WriteLine(node.BYNAVN);
        }

        public Node ROOT { set { this.Root = value; } get { return this.Root; } }

    }
}
